#include <bits/stdc++.h>
using namespace std;

/*
3195. 包含所有 1 的最小矩形面积 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

 

示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：



这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]

输出： 1

解释：



这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

 

提示：

1 <= grid.length, grid[i].length <= 1000
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有一个 1 。
*/

// 法一
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        // 初始化 边界值 --> 正确更新
        int row = grid.size();
        int col = grid[0].size();

        int maxRow = -1, minRow = row;
        int maxCol = -1, minCol = col;
        
        // 网格遍历 查找全部1的边界
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    minRow = min(minRow, i);
                    maxRow = max(maxRow, i);
                    minCol = min(minCol, j);
                    maxCol = max(maxCol, j);
                }
            }
        }
        // rect Area
        int height = maxRow - minRow + 1;
        int width = maxCol - minCol + 1;

        return height * width;
    }
};

// 法二
// 四个方向的收缩边界
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 初始化边界：up(上边界)、left(左边界)、right(右边界)、down(下边界)
        int up = 0, left = 0, right = n - 1, down = m - 1;
        
        // 从顶部开始收缩上边界：找到最上方包含1的行
        for (int i = 0; i < m; i++) {
            int flag = 0; // 标记当前行是否有1
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    flag = 1; // 当前行有1，标记为1
                    break;
                }
            }
            if (flag == 0) {
                up++; // 当前行无1，上边界上移
            } else {
                break; // 找到首个含1的行，停止上边界收缩
            }
        }
        
        // 从底部开始收缩下边界：找到最下方包含1的行
        for (int i = m - 1; i >= 0; i--) {
            int flag = 0; // 标记当前行是否有1
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    flag = 1; // 当前行有1，标记为1
                    break;
                }
            }
            if (flag == 0) {
                down--; // 当前行无1，下边界下移
            } else {
                break; // 找到首个含1的行，停止下边界收缩
            }
        }
        
        // 从右侧开始收缩右边界：找到最右侧包含1的列
        for (int j = n - 1; j >= 0; j--) {
            int flag = 0; // 标记当前列是否有1
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 1) {
                    flag = 1; // 当前列有1，标记为1
                    break;
                }
            }
            if (flag == 0) {
                right--; // 当前列无1，右边界左移
            } else {
                break; // 找到首个含1的列，停止右边界收缩
            }
        }
        
        // 从左侧开始收缩左边界：找到最左侧包含1的列
        for (int j = 0; j < n; j++) {
            int flag = 0; // 标记当前列是否有1
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 1) {
                    flag = 1; // 当前列有1，标记为1
                    break;
                }
            }
            if (flag == 0) {
                left++; // 当前列无1，左边界右移
            } else {
                break; // 找到首个含1的列，停止左边界收缩
            }
        }
        
        // 计算最小矩形面积：(高度) * (宽度)
        return (down - up + 1) * (right - left + 1);
    }
};